/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: 邹陆川
 * @Date: 2022/04/19/12:18 下午
 * @Description:插入排序
 * 核心思想：
 *    将一个记录插到一个已经排好序的有序表中，从而得到一个新的排好序的有序表，记录数据增1。
 *    使用双层循环，外层循环控制除第一个元素外的遍历，内层循环控制与元素比较的次数
 *    时间复杂度：外层循环n次，内层也是n次，故时间复杂度O = （n*n）
 */
public class InsertSort {
  static void sort(Integer[] arr){
    //定义一个临时变量
    int temp;
    for (int i = 1; i < arr.length; i++) {
      for (int j = i; j > 0; j--) {
        //遇到比当前值还要大的则交换
        if(arr[j] < arr[j-1]){
          //交换位置
          temp = arr[j-1];
          arr[j-1] = arr[j];
          arr[j] = temp;
        }else{
          //由于是已经排好序列的有序表，所以当不满足
          break;
        }
      }
    }
  }
}
